package com.weecee.zs.utils.al;

import org.apache.commons.lang3.ArrayUtils;
import org.junit.Test;

/**
 * Copyright ©2016
 *
 * @author shuai.zhang  on 2017/3/16
 * @version 1.0.0
 * @description
 */
public class QS {


	int partition(int[] array, int p, int q) {
		int i = p;
		int m = i;
		int mv = array[i];

		for (int j = p + 1; j <= q; ) {
			if (array[j] < array[m]) {
				i++;
				int temp = array[i];
				array[i] = array[j];
				array[j] = temp;
			}
			j++;
		}
		array[m] = array[i];
		array[i] = mv;
		return i;
	}


	void quickSort(int[] array, int p, int q) {
		if (p < q) {
			int m = partition(array, p, q);
			quickSort(array, p, m - 1);
			quickSort(array, m + 1, q);
		}
	}

	@Test
	public void TestQucikSort() {
		int[] array = {1111, 5, 2, 8, 10, 1, 2, 22222};
		quickSort(array, 0, array.length - 1);
		System.out.println(ArrayUtils.toString(array));
	}
}
